package merge_slice

import (
	"cmp"
	"slices"
)

// 合并后排序
// 先将两个数组合并，再排序
func Merge1[T cmp.Ordered](s1, s2 []T, m, n int){
	s1 = s1[:m]
	s2 = s2[:n]
	s1 = append(s1, s2...)
	slices.Sort(s1)
}

// 双指针
func Merge2[T cmp.Ordered](s1, s2 []T, m, n int) {
	var (
		ptr1, ptr2  int
		cur  T
		sorted = make([]T, 0, m+n)
	)

	for ptr1 < m || ptr2 < n {
		if ptr1 == m {
			cur = s2[ptr2]
			ptr2++
		} else if ptr2 == n {
			cur = s1[ptr1]
			ptr1++
		} else if s1[ptr1] <= s2[ptr2] {
			cur = s1[ptr1]
			ptr1++
		} else {
			cur = s2[ptr2]
			ptr2++
		}
		sorted = append(sorted, cur)
	}
	for i, num := range sorted {
		s1[i] = num
	}
}

// 逆向双指针
// 因为是非递减数组，所以从后往前遍历，不断取两个组中的较大值放入s1中
func Merge3[T cmp.Ordered](s1, s2 []T, m, n int){
	var (
		i = m - 1
		j = n - 1
		k = m + n - 1
	)
	for j >= 0 {
		if i < 0 || s1[i] < s2[j] {
			s1[k] = s2[j]
			j--
		} else {
			s1[k] = s1[i]
			i--
		}
		k--
	}
}
